/**
 * 带头结点的链式栈实现
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct SNode{
	int data;
	struct SNode* next;
}SNode, *LinkedStack;

//初始化
bool init(LinkedStack &stack);

//入栈
bool push(LinkedStack &stack, int data);

//出栈
int pop(LinkedStack &stack);

//便利当前栈的元素(栈底->栈顶)
void print(LinkedStack &stack);

int main()
{
	LinkedStack stack=NULL;
	init(stack);
	push(stack,1);
	push(stack,2);
	push(stack,3);
	push(stack,4);
	push(stack,5);
	push(stack,6);
	print(stack);
	printf("出栈:%d\n",pop(stack));
	print(stack);
	printf("出栈:%d\n",pop(stack));
	print(stack);
	printf("出栈:%d\n",pop(stack));
	print(stack);
	printf("出栈:%d\n",pop(stack));
	print(stack);
	return 0;
}

bool init(LinkedStack &stack)
{
	SNode* newNode=(SNode* )malloc(sizeof(SNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=-1;
	stack=newNode;
	return true;
}

bool push(LinkedStack &stack, int data)
{
	LinkedStack stack_node=stack;
	SNode* newNode=(SNode* )malloc(sizeof(SNode));
	if(!newNode) return false;
	newNode->data=data;
	newNode->next=NULL;
	
	while(stack_node->next) stack_node=stack_node->next;
	stack_node->next=newNode;
	return true;
}

int pop(LinkedStack &stack)
{
	SNode* stack_node=stack->next;
	SNode* pre_stack_node=stack;
	SNode* delete_node=NULL;
	if(!stack_node->next) return -1;
	while(stack_node->next)
	{
		pre_stack_node=stack_node;
		stack_node=pre_stack_node->next;
	}
	
	delete_node=stack_node;
	pre_stack_node->next=NULL;
	stack_node=stack->next;
	int returnData=delete_node->data;
	free(delete_node);
	delete_node=NULL;
	return returnData;
}

void print(LinkedStack &stack)
{
	LinkedStack stack_node=stack->next;
	while(stack_node)
	{
		printf("%d ",stack_node->data);
		stack_node=stack_node->next;
	}
	printf("\n");
}